#include <stdio.h>
#include <string.h>

int ViolentMatch(char* s, char* p)
{
  int sLen = strlen(s);
  int pLen = strlen(p);

  int i = 0; int j = 0;
  while (i < sLen && j < pLen) {
    if (s[i] == p[j]) {
      ++i;
      ++j;
    } else {
      i = i - j + 1;
      j = 0;
    }
  }

  if (j == pLen) {
    return i - j;
  }
  return -1;
}

void GetNext(char* p, int next[])
{
  int pLen = strlen(p);
  next[0] = -1;
  int k = -1;
  int j = 0;

  while (j < pLen - 1) {
    if (k == -1 || p[j] == p[k]) {
      ++k;
      ++j;
      next[j] = k;
    } else {
      k = next[k];
    }
  }
}

int KmpSearch(char* s, char* p)
{
  int i = 0, j = 0;
  int sLen = strlen(s);
  int pLen = strlen(p);
  while (i < sLen && j < pLen) {
    if (j == -1 || s[i] == p[j]) {
      ++i, ++j;
    } else {
      j = next[j];
    }
  }

  if (j == pLen) {
    return i - j;
  }
  return -1;
}

int main(int argc, char* argv[])
{
  return 0;
}

